package text;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	 public static void main(String[] args) {
		 
		 int[] arr = {2,4,9,5,1};
		 Main heapSortDemo = new Main();
		 heapSortDemo.heapSort(arr);
		 System.out.println(Arrays.toString(arr));
	 }
	 
	 
	 public void heapSort(int[] arr) {
		 if(arr.length == 0) {
			 return;
		 }
		 //1、初始化堆
		 for(int i = arr.length/2-1; i>=0; i--) {
			 adjust(arr, i, arr.length);
		 }
		 
		 System.out.println("1:"+Arrays.toString(arr));
		 int temp;
		 //2、交换收尾元素，并继续构建堆结构
		 for(int i = arr.length - 1; i > 0; i-- ) {
			 //交换收尾元素
			 temp = arr[0];
			 arr[0] = arr[i];
			 arr[i] = temp;
			 System.out.println("2:"+Arrays.toString(arr));
			 //并继续构建堆结构
			 adjust(arr, 0, i);		 
		 }
		 
	 }

	 
	 
	 /**
	  * 退排序（升序）
	  * @param arr 待排序的数组
	  * @param i  父节点在数组中的下标
	  * @param length  数组的长度
	  */
	 public void adjust(int[] arr, int i, int length) {
		 if(arr.length == 0) {
			 return;
		 }
		 int temp = arr[i];
		 for(int j = i*2+1; j < length; j = j*2+1) {
			 
			 if(j+1 < length && arr[j+1] > arr[j]) {
				 j++;
			 }
			 if(arr[j] > temp) {
				 arr[i] = arr[j];
				 i = j;
			 }else {
				 break;
			 }
		 }
		 arr[i] = temp;	 
	 }
    	
}
